Queues

 

Introduction

Queue is a simple but very powerful data structure to solve numerous computer applications. Like stacks, queues are also useful to solve various system programs. Let us visit some simple applications of queues in our everyday life as well as in computer science before going to study this data structure.

Queuing in front of a counter

Suppose there are a number of customer in front of a counter to get service (say, to collect tickets or to withdraw/deposit money in a teller of a bank), Figure 7.1(a). The customers are forming a queue and they will be served in the order they arrived, that is, a customer who comes first will be served first.

 

Fig. 7.1(a)  Queue of customers.

Traffic control at a turning point

Suppose there is a turning point in a highway where the traffics has to turn, Figure 7.1(b). All the traffics will wait on a line till it gets the signal for moving. And on getting the ‘Go’ signal the vehicles will turn on a first come first turn basis.

 

 

Fig. 7.1(b)  Traffic passing at a turning point.

Process synchronization in multi-user environment

In multi-user environment, more than one processes are to be handled by the monitor (operating system), Figure 7.1(c). The three different states that a process may have: READY, RUNNING and AWAITED. Processes are in READY state when they are submitted to the system for execution. A process is in RUNNING state if it is currently under execution. Similarly a process will be transferred to the AWAITED state when it requires resource(s) which is/are busy. In order to synchronize the execution of processes, monitor has to maintain two queues namely Q1 and Q2 for READY and AWAITED states respectively where processes entered a queue first will be exited first.

 

 

Fig. 7.1(c)  Queues of processes.

Resource sharing in a computer centre

In a computer centre, where resources are limited as compared to the demand, user must sign a waiting register, Figure 7.1(d). The user, who has been waiting for a terminal for the longest period of time gets hold of the resource first then the second candidate and so on. Here the waiting list maintains a queue and the first signed will be allowed first.

 

 

Fig. 7.1(d)  Waiting queue of users in computer centre.

Definition

Like stack, a queue is an ordered collection of homogeneous data elements; in contrast with the stack, here, insertion and deletion operations take place at two extreme ends.

        Queue is also a linear data structure like array, stack and linked list where ordering of the elements are in linear fashion. The only difference between stack and queue is that in case of stack insertion and deletion (PUSH and POP) operations are at one end (TOP) only, but in a queue insertion (called ENQUEUE) and deletion (called DEQUEUE) operations take place at two ends called REAR and FRONT of the queue respectively. Figure 7.2 represents a model of queue structure.

 

 

Fig. 7.2  Model of a queue.

 

Elements in a queue are termed as ITEM; the number of elements that a queue can accommodate is termed as LENGTH.

        From the examples as mentioned and the definition stated above, it is evident that data in queue is processed in the same order as it was entered, that is, on a first in, first out basis. This is why, queue is also alternatively termed as first-in first-out (FIFO).

Representation of Queues

There are two ways to represent a queue in memory:

        1. Using an array

        2. Using linked list

First kind of representation uses one-dimensional array and it is a better choice where a queue of fixed size is required. The other representation uses a double linked list and provides a queue whose size can vary during processing.

        Following two sub sections are to describe the representation of queues in memory.

Representation of Queue using Array

A one-dimensional array, say Q[1 . . . N] can be used to represent a queue. Figure 5.3 shows an instance of such a queue. With this representation, two pointers, namely, FRONT and REAR are used to indicate two ends of the queue. For the insertion of the next element, pointer REAR will be consultant and for deletion pointer FRONT will be consultant.

 

 

Fig. 5.3  Array representation of a queue.

 

        Three states of the queue with this representation are as below:

        Queue is empty

                FRONT = 0

                REAR = 0    (and/or)

        Queue is full

                REAR = N                                                   

                FRONT = 1    (when full by compact)

        Queue contains element ³ 1

                FRONT £ REAR                                                                                                                                

                Number of element = REAR – FRONT + 1

Now let us define the operation ENQUEUE to insert an element into a queue.

 

Algorithm Enqueue

Input:  An element ITEM that has to be inserted.

Output:  The ITEM is at the REAR of the queue.

Data structure:  Q is the array representation of queue structure; two pointers FRONT and REAR of the

               queue Q are known.

Steps:

1.	If (REAR = N) then                                                                                                        // Queue is full
2.		Print “Queue is full”
3.		Exit
4.	Else
5.		If (REAR = 0) and (FRONT = 0)  then                                                         // Queue is empty
6.			FRONT = 1
7.		EndIf
8.		REAR = REAR + 1                                                     // Insert the item into the queue at REAR
9.		Q[REAR] = ITEM
10.	EndIf
11.	Stop

 

The deletion operation DEQUEUE can be defined as below:

 

Algorithm Dequeue

Input:       A queue with elements. FRONT and REAR are the two pointers of the queue Q.

Output:  The deleted element is stored in ITEM.

Data structures:  Q is the array representation of queue structure.

Steps:

1.	If (FRONT = 0) then
2.		Print “Queue is empty”
3.		Exit
4.	Else
5.		ITEM = Q[FRONT]                                                                                       // Get the element
6.		If (FRONT = REAR)                                                     // When queue contains single element
7.			REAR = 0                                                                            // The queue becomes empty
8.			FRONT = 0
9.		Else
10.			FRONT = FRONT + 1
11.		EndIf
12.	EndIf
13.	Stop

 

Let us trace the above two algorithms with a queue of size = 10. Suppose, the current state of the queue is FRONT = 8, REAR = 9. Ten operations are requested as under:

                                       1. DEQUEUE         2. ENQUEUE         3. ENQUEUE           

                                      4. DEQUEUE         5. DEQUEUE       6. DEQUEUE           

                                      7. ENQUEUE         8. ENQUEUE         9. DEQUEUE           

                                    10. DEQUEUE

 

Figure 7.4 presents the status of the queue when these operations are carried out.

 

Fig. 7.4  Operations on a queue.

        There is one potential problem with this representation. From Figure 7.4, we can see that with this representation, a queue may not be full, still a request for insertion operation may be denied. For an example, on request (3) (in Figure 7.4) 8 rooms are available but insertion is not possible as insertion pointer reaches the end of the queue. This is simply a wastage of the storage. This type of representation is recommendable for such application where the queue is emptied at certain interval.

Representation of Queue using Linked List

One more limitation of a queue, other than the inadequate service of insertion represented with array, is the rigidness of its length. In several applications, length of the queue may not be predicated before and it varies abruptly. To overcome this problem, another preferable representation of queue is with linked list. Here, we select double linked list which allows us to move both the ways. Figure 7.5 shows the double, linked list representation of a queue. Pointers FRONT and REAR point the first node and the last node in the list.

 

 

Fig. 7.5  A double linked list representation of queue.

 

 

        Two states of the queue, namely, empty or it contains some element can be judged by the following tests:

        Queue is empty

              FRONT = REAR = HEADER

              HEADER→RLINK = NULL

 

        Queue contains at least one element

              HEADER→RLINK ¹ NULL

The insertion and deletion operations are straightforward and the same as in the algorithm InsertEnd_DL (for Enqueue) and algorithm DeleteFront_DL (for Dequeue); these two algorithms are already defined in Module 5 (Linked List).

 

Various Queue Structures

So far we have discussed two different queue structures, that is, using array and linked list (and a variation of queue structure using array as an assignment). Other than these, there are more known queue structures. This section discusses about them.

Circular Queue

For a queue represented using array when the REAR pointer reaches at the end, insertion will be denied even if room is available at the front. One way to avoid this is using a circular array. Physically, a circular array is the same as ordinary array, say, A[1 . . . N], but logically it implies that A[1] comes after A[N] or after A[N], A[1] appears. Figure 7.6 shows logical and physical representations for a circular array.

 

 

Fig. 7.6  Logical and physical views of a circular queue.

 

        The principle for representation of a circulation array is as stated below:

        Both pointers will move in clockwise direction. This is controlled by the mod operation; for example, if the current pointer is at i then shift to the next location will be i mod LENGTH + 1, 1 £ i £ LENGTH (where LENGTH is the queue length). Thus, if i = LENGTH (that is at the end), then next position for the pointer is 1.

        With this principle the two states of the queue regarding its empty or full will be decided as:

       

        Circular queue is empty

              FRONT = 0

              REAR = 0

        Circular queue is full

              FRONT = (REAR mod LENGTH) + 1

        Following two algorithms describe the insertion and deletion operations on a circular queue.

 

Algorithm Enqueue_CQ

Input:  An element ITEM to be inserted into the circular queue.

Output:  Circular queue with the ITEM at FRONT, if the queue is not full.

Data structures:  CQ be the array to represent the circular queue. Two pointers FRONT and REAR are

                            known.

Steps:

1.	If (FRONT = 0) then                                                                                       // When queue is empty
2.		FRONT = 1
3.		REAR = 1
4.		CQ[FRONT] = ITEM
5.	Else                                                                                                                      // Queue is not empty
6.		next = (REAR mod LENGTH) + 1
7.		If (next ¹ FRONT) then                                                                             // If queue is not full
8.			REAR = next
9.			CQ[REAR] = ITEM
10.		Else
11.			Print “Queue is full”
12.		EndIf
13.	EndIf
14.	Stop

 

Algorithm Dequeue_CQ

Input:   A queue CQ with elements. Two pointers FRONT and REAR are known.

Output:  The deleted element is ITEM if the queue is not empty.

Data structures:  CQ is the array representation of circular queue.

Steps:

1.	If (FRONT = 0) then
2.		Print “Queue is empty”
3.		Exit
4.	Else
5.		ITEM = CQ[FRONT]
6.		If (FRONT = REAR) then                                             // If the queue contains single element
7.			FRONT = 0
8.			REAR = 0
9.		Else
10.			FRONT = (FRONT mod LENGTH) + 1
11.		EndIf
12.	EndIf
13.	Stop

 

        In order to trace these two algorithms let us consider a circular queue of LENGTH = 4. Following operations are requested. Different states of the queue under processing these requests is illustrated in Figure 7.7.

 

                          1.   ENCQUEUE (A)                                        2.   ENCQUEUE (B)

                          3.   ENCQUEUE (C)                                       4.   ENCQUEUE (D)

                          5.   DECQUEUE                                               6.   ENCQUEUE (E)

                          7.   DECQUEUE                                              8.   ENCQUEUE (F)

                          9.   DECQUEUE                                             10.   DECQUEUE

                        11.   DECQUEUE                                             12.   DECQUEUE

 

        Assume that initially queue is empty, that is, FRONT = REAR = 0.

 

 

 

 

Fig. 7.7  Trace of insertion and deletion operations on a circular queue.

 

 

Deque

Another variation of the queue is known as deque (may be pronounced as ‘deck’). Unlike queue, in deque, both insertion and deletion operations can be made at either end of the structure. Actually, the term deque is originated from double ended queue. Such a structure is shown in Figure 7.8.

 

 

 

Fig. 7.8 A deque structure.

 

 

        It is clear from the deque structure that it is a general representation of both stack and queue. In other words, a deque can be used as a stack as well as a queue.

        There are various ways of representing a deque in a computer. One simpler way to represent it is using a double linked list. Another popular representation is using a circular array (as used in circular queue).

       

 

Following four operations are possible on a deque which consists of a list of items:

        1. Push_DQ(ITEM) :  To insert ITEM at the FRONT end of deque

        2. Pop_DQ( ):  To remove the FRONT item from deque

        3. Inject(ITEM):  To insert ITEM at the REAR end of deque.

        4. Eject( ):  To remove the REAR ITEM from deque.

        These operations are described for a deque based on a circular array of length LENGTH. Let the array be DQ[1 . . . LENGTH].

     

Algorithm Push_DQ

Input:  ITEM to be inserted at the FRONT.

Output:  Deque with newly inserted element ITEM if it is not full already.

Data structures:  DQ being the circular array representation of deque.

Steps:

1.	If (FRONT = 1) then                                                                            // If FRONT is at extreme left
2.		ahead = LENGTH
3.	Else                                                                        // If FRONT is at extreme right or deque is empty
4.		If (FRONT = LENGTH) or (FRONT = 0) then
5.			ahead = 1
6.		Else
7.			ahead = FRONT – 1                                         // FRONT is at an intermediate position
8.		EndIf
9.		If (ahead = REAR) then
10.			Print “Deque is full”
11.			Exit
12.		Else
13.			FRONT = ahead                                                                                   // Push the ITEM
14.			DQ[FRONT] = ITEM
15.		EndIf
16.	EndIf
17.	Stop

 

 

Algorithm Pop_DQ

        /* This algorithm is same as the algorithm Dequeue_CQ  */

 

Algorithm Inject

        /* This algorithm is same as the algorithm Enqueue_CQ */

 

Algorithm Eject_DQ

Input:  A deque with elements in it.

Output:  The item is deleted from the REAR end.

Data structures:  DQ being the circular array representation of deque.

Steps:

1.	If (FRONT = 0) then
2.		Print “Deque is empty”
3.		Exit
4.	Else
5.		If (FRONT = REAR) then                                               // The deque contains single element
6.			ITEM = DQ[REAR]
7.			FRONT = REAR = 0                                                                 // Deque becomes empty
8.		Else
9.			If (REAR = 1) then                                                                  // REAR is at extreme left
10.				ITEM = DQ[REAR]
11.				REAR = LENGTH
12.			Else
13.				If (REAR = LENGTH) then                                      // REAR is at extreme right
14.					ITEM = DQ[REAR]
15.					REAR = 1
16.				Else                                                           // REAR is at an intermediate position
17.					ITEM = DQ[REAR]
18.					REAR = REAR – 1
19.				EndIf
20.			EndIf
21.		EndIf
22.	EndIf
23.	Stop

 

        There are, however, two variations of deque  known:

        1. Input restricted deque, and

        2. Output restricted deque.

        These two types are actually intermediate between a queue and a deque. Specifically, an input-restricted deque is a deque which allows insertions at one end (say REAR end) only but allows deletions at both ends. Similarly, an output-restricted deques is a deque where deletions take place at one end (say FRONT end) only but allows insertions at both ends. Figure 7.9 represents two such variations of deques.

 

 

 

Fig. 7.9  Types of deque.

 

 

Priority Queue

A priority queue is another variation of queue structure. Here, each element has been assigned a value, called priority of the element, and an element can be inserted or deleted not only at the ends but at any position on the queue. Figure 7.10 shows a priority queue.

 

 

Fig. 7.10  View of a priority queue.

 

        With this structure, an element X of priority p_i may be deleted before an element which is at FRONT. Similarly, insertion of an element is based on its priority, that is, instead of adding it after the REAR it may be inserted at an intermediate position dictated by its priority value.

        Note that, the name priority queue is a misnomer in the sense that the data structure is not a queue as per the definition; priority queue does not strictly follow first-in first-out (FIFO) principle which is the basic principle of a queue. Nevertheless, the name is now firmly associated with this particular data type. However, there are various models of priority queue known in different applications. Let us consider a particular model of priority queue.

       1.   An element of higher priority is processed before any element of lower priority.

       2.   Two elements with the same priority are processed according to the order in which they were added to the queue.

Here, process means two basic operations namely insertion or deletion. There are various ways of implementing the structure of a priority queue. These are

          (i)  Using a simple/circular array

         (ii)  Multi-queue implementation

        (iii)  Using a double linked list, and

        (iv)  Using heap tree.

Priority queue using an array

With this representation, an array can be maintained to hold the item and its priority value. The element will be inserted at the REAR end as usual. The deletion operation will then be performed either of the two following ways:

        (a) Starting from the FRONT pointer, traverse the array for an element of the highest priority. Delete this element from the queue. If this is not the front most element shift all its trailing elements after the deleted element one stroke each to fill up the vacant position (see Figure 7.11).

Fig. 7.11  Deletion operation in an array representation of a priority queue.

 

        This implementation, however, is very inefficient as it involves searching the queue for the highest priority element and shifting the trailing elements after the deletion. A better implementation is as follows:

        (b) Add the elements at the REAR end as earlier. Using a stable sorting algorithm*, sort the elements of the queue so that the highest priority elements is at the FRONT end. When a deletion is required, delete it from the FRONT end only (see Figure 7.12).

 

 

Fig. 7.12  Another array implementation of a priority queue.

 

        The second implementation is comparatively better than the first one, here the only burden is to sort the elements. The algorithms of the above two implementations are left as assignments to the reader.

Multi-queue implementation

This implementation assumes N different priority values. For each priority P_i there are two pointers F_i and R_i corresponding to FRONT and REAR pointer respectively. The elements between F_i and R_i are all of equal priority value P_i. Figure 5.14 represents a view of such structure.

 

 

Fig. 5.14  Multi-queue representation of a priority queue.

 

        With this representation, an element with priority value P_i will consult F_i for deletion and R_i for insertion. But this implementation is associated with number of difficulties:

          (i)   It may lead to a huge shifting in order to make a room for an item to be inserted.

         (ii)   Large number of pointers are involved when the range of priority values are large.

In addition to the above, there are two other techniques to represent multi-queue, which are shown in Figures 7.14(a) and 7.14(b).

        It is clear from Figure 7.14(a) that for each priority value a simple queue is to be maintained. An element will be added into a particular queue depending on its priority value.

        The priority queue as shown in Figure 7.14(b) is some way better than the multi-queue with multiple queues. Here one can get rid off maintaining several pointers for FRONT and REAR in several queues. Multi-queue with multiple queues has one advantage that one can have different queues of arbitrary length. In some application, it is seen that, number of occurrence of elements with some priority value is much larger than other value, thus demanding a queue of larger size.

 

 

Fig. 7.14  Multi-queue implementation with multiple simple queues and matrix.

 

        Both the above representations are not economic from the memory utilization point of view; majority of the memory space remains vacant.                                                           

        Algorithms for insertion and deletion operations for multi-queue implementation are left as exercises.

Linked list representation of priority queue

This representation assumes the node structure as shown in Figure 7.15. LLINK and RLINK are two usual link fields, DATA is to store the actual content and PRIORITY is to store the priority value of the item. We will consider FRONT and REAR as two pointers pointing the first and last node in the queue, respectively. Here all the nodes are in sorted order according to the priority values of the items in the nodes. Following is an instance of priority queue:

 

 

Fig. 7.15  Linked list representation of a priority queue.

 

        With this structure, to delete an item having priority p, the list will be searched starting from the node under pointer REAR and the first occurring node with PRIORITY = p will be deleted. Similarly, to insert a node containing an item with priority p, the search will begin from node under pointer FRONT and node will be inserted before a node found first with priority value p, or if not found then before the node with the next priority value. The following two algorithms Insert_PQ and Delete_PQ are used to implement the insertion and deletion operations on a priority queue.

 

Algorithm Insert_PQ

Input:  The ITEM and its priority P value of a node that is to be inserted.

Output:  A new node inserted.

Data structures:  Linked list structure of priority queue; HEADER as the pointer to the header.

Steps:

1.	ptr = HEADER                                                                                             // Start from the first node
2.	new = GetNode(NODE)                                                                                         // Avail a new node
3.	new→DATA = ITEM                                                                // Get initialized the node with ITEM
4.	new→PRIORITY = P
5.	While (ptr→RLINK ¹ NULL) and (ptr→PRIORITY < P) do                    // Search for the position
6.		ptr = ptr→RLINK
7.	EndWhile
8.	If (ptr→RLINK = NULL) then     // If the list is empty or the item is with the largest priority value
9.		ptr→RLINK = new
10.		new→LLINK = ptr
11.		new→RLINK = NULL                                                   // The node is inserted as the last node
12.		REAR = new
13.	Else
14.		If (ptr→PRIORITY ³ P) then                                                          // First occurrence is found
15.			ptr1 = ptr→.LLINK                                                                         // Insert the new node
16.			ptr1→RLINK = new                                                 // Before the node with priority > P
17.			new→RLINK = ptr
18.			ptr→LLINK = new
19.			new→LLINK = ptr1
20.		EndIf
21.	EndIf
22.	FRONT = HEADER→RLINK                                                                     // Set the FRONT pointer
23.	Stop

 

        Similarly, the algorithm for deletion can be described as below:

 

Algorithm Delete_PQ

Input:  The priority P of the element which has to be deleted.

Output:  The element that is being deleted.

Data structures:  Linked list structure of priority queue; HEADER as the pointer to the header.

Steps:

1.	If (REAR = NULL) then
2.		Print “Queue is empty”
3.		Exit
4.	Else
5.		ptr = REAR
6.		While (ptr→PRIORITY > P) and (ptr ¹ HEADER) do
7.			ptr = ptr→LLINK
8.		EndWhile
9.		If (ptr = HEADER) or (ptr→PRIORITY < P)
10.			Print “No item with priority”, P
11.			Exit
12.		Else
13.			If (ptr→priority = P) then
14.				ptr1 = ptr→LLINK
15.				ptr2 = ptr→RLINK
16.				If (ptr = REAR)                                                     // If the last node to be deleted
17.					REAR = ptr1
18.					ptr1→RLINK = NULL
19.				Else                                                                                    // Other than last node
20.					ptr1→RLINK = ptr2                                                                   // Deleted
21.					ptr2→LLINK = ptr1
22.				EndIf
23.			EndIf
24.		EndIf
25.		item = ptr→DATA
26.		ReturnNode(item)
27.	EndIf
28.	Stop

               

Application of Queues

Numerous applications of queue structures are known in computer science. One major application of queue is in simulation. Another important application of queue is observed in implementation of various aspects of operating system. Multiprogramming environment uses several queues to control various programs. And, of course, queues are very much useful to implement various algorithms. For example, various scheduling algorithms are known to use varieties of queue structures.

        This section highlights few applications and then illustrates how powerful queues are there to solve different problems.

 

CPU Scheduling in Multiprogramming Environment

In a multiprogramming environment, a single CPU has to serve more than one program simultaneously. This section gives a brief idea about how queues are important to manage various programs in such an environment.

        Let us consider a multiprogramming environment where possible jobs to the CPU are categorized into three groups:

        1.  Interrupts to be serviced. Variety of devices and terminals are connected with the CPU and they may interrupt at any moment to get a service from it.

        2.  Interactive users to be serviced. These are mainly student’s programs in various terminals under execution.

        3.  Batch jobs to be serviced.

        These are long term jobs mainly from the non-interactive users, where all the inputs are fed when jobs are submitted; simulation programs, and jobs to print documents are of this kind.

        Here the problem is to schedule all sorts of jobs so that the required level of performance of the environment will be attained. One way to implement complex scheduling is to classify the workload according to its characteristics and to maintain separate process queues. So far the environment is concerned, we can maintain three queues, as depicted in Figure 7.19. This approach is often called multi-level queues scheduling. Process will be assigned to their respective queues. CPU will then service the processes as per the priority of the queues. In case of a simple strategy, absolute priority, the process from the highest priority queue (for example, system processes) are serviced until the queue becomes empty. Then CPU switches to the queue of interactive processes which is having medium-priority and so on. A lower-priority process may, of course, be pre-empted by a higher-priority arrival in one of the upper-level queues.

 

 

Fig. 7.19 Process scheduling with multi-level queues.

 

        Multi-level queues strategy is a general discipline but has some drawbacks. The main drawback is that when process arrived in higher-priority queues is very high, the processes in lower-priority queue may starve for a long time. One way out to solve this problem is to time slice between the queues. Each queue gets a certain portion of the CPU time. Another possibility is known as multi-level feedback queue strategy. Normally in multi-level queue strategy, as we have seen, processes are permanently assigned to a queue upon entry to the system and processes do not move among queues. Multi-level feedback queue strategy, on the contrary, allows a process to move between queues. The idea is to separate out processes with different CPU burst characteristics. If a process uses too much CPU time (that is long run process), it will be moved to a lower-priority queue. Similarly, a process which waits too long in a lower-priority queue may be moved to a higher-priority queue. For example, consider a multi-level feedback queue strategy with three queues Q₁, Q₂ and Q₃ (Fig. 7.20).

 

 

Fig. 7.20  A multi-level feedback queue.

 

        A process entering the system is put in queue Q₁. A process in Q₁ is given a time quantum t of 10 ms, say. If it does not finish within this time, it is moved to the tail of queue Q₂. If Q₁ is empty, the process at the front of queue Q₂ is given a time quantum t of 20 ms, say. If it does not complete within this time quantum, it is pre-empted and put into queue Q₃. Processes in queue Q₃ are serviced only when queues Q₁ and Q₂ are empty.

        Thus, with this strategy, CPU first executes all processes in queue Q₁. Only when Q₁ is empty it will execute all processes in queue Q₂. Similarly, processes in queue Q₃ will only be executed if queues Q₁ and Q₂ are empty. A process which arrives in queue Q₁ will pre-empt a process in queue Q₂ or Q₃.

        It can be observed that, this strategy gives the highest priority to any process with a CPU burst of 10 ms or less. Processes which need more than 10 ms, but less than or equal to 20 ms are also served quickly, that is, it gets the next highest priority than the shorter processes. Longer processes automatically sink to queue Q₃, from Q₃, processes will be served in first-come first-serve (FCFS) basis and in case of process waiting for a too long time (as decided by the scheduler) may be put into the tail of queue Q₁.

Round Robin Algorithm

Round robin (RR) algorithm is a well-known scheduling algorithm and is designed especially for time sharing systems. Here, we will see how a circular queue can be used to implement such an algorithm. Before going to implement the RR algorithm, we should first describe the algorithm with illustration. Suppose, there are n processes P₁, P₂, . . ., P_n required to be served by the CPU. Different processes require different execution time. Suppose, sequence of processes’ arrivals are according to their subscripts, that is, P₁ comes first than P₂ and in general, P_i comes after P_i–1 for 1 < i £ n.

        RR algorithm first decides a small unit of time, called a time quantum or time slice, t. A time quantum is generally from 10 to 100 milliseconds. CPU starts services with P₁. P₁ gets CPU for t instant of time, afterwards CPU switches to P₂ and so on. When CPU reaches the end of time quantum of P_n it returns to P₁ and the same process will be repeated. Now, during time sharing, if a process finishes its execution before the finishing of its time quantum, the process then simply releases the CPU and the next process waiting will get the CPU immediately.

        For an illustration, consider Table 5.1 for the set of processes:

 

Table 5.1  Table for Process and Burst Time

                                                         P₁                                                                                  7

                                                         P₂                                                                              18

 

        The total CPU time required is 30 unit. Let us assume a time quantum of 4 unit. The RR scheduling for this will be as shown in Figure 7.21.

 

 

Fig. 7.21  RR scheduling.

 

        The advantages of this kind of scheduling is reducing the average turn around time (not necessarily true always). Turn around time of a process is the time of its completion – time of its arrival. Thus, using FCFS strategy,

                       Average turn around time = unit

Whereas, using RR algorithm,

                                   Average turn around time unit

See the result by repeating the calculations but using the sequence of processes as P₂, P₁
and P₃.

        In time sharing systems any process may arrive at any instant of time. Generally, all the process currently under executions, are maintained in a queue. When a process finishes its execution this process is deleted from the queue and whenever a new process arrives it is inserted at the tail of the queue and wait for its turn. To illustrate this, let us consider Table 7.2.

Table 7.2  Table for Process Events

                                    P₁                                                                                                                                                 0                                           9

                                    P₂                                                                                                                                                 1                                           3

                                    P₃                                                                                                                                                 9                                           5

 

Total CPU time required is 25 units. Let the time quantum be t = 5 unit. Figure 5.23 illustrates the snapshot at various instants with RR scheduling.

 

 

Fig. 7.22  In and out in a queue during RR scheduling.

 

        Now let us discuss the implementation of RR scheduling algorithm. Circular queue is the best choice for it. If may be noted that it is not strictly a circular queue because here a process when it completes its execution required to be deleted from the queue and it is not necessarily from the front of the queue rather from any position of the queue. Except this, it follows all the properties of queue, that is, processes which comes first gets its turn first.

        Implementation of the RR algorithm using a circular queue is straightforward. Here, we use variable sized circular queue; size of the queue at any instant is decided by the number of processes in execution at that instant. Another mechanism is necessary; whenever a process is deleted, to fill the space of deleted process, it is required to squeeze all the processes preceding to it starting from the front pointer (Fig. 7.23). (Detail procedure for implementation is left as an exercise to the reader.)

 

Fig. 7.23  Deletion of a process from circular queue.

 

 

Queue with Java Collection Framework

 

The Queue is an ordered list of objects with its use limited to insert elements at the end of the list and deleting elements from the start of list, that is, it follows the FIFO or the First-In-First-Out principle.

 

To facilitates the queue structure and its variants, java.util package provides the Queue interface which and extends the Collection interface (see Figure 7.24).

 

The another variants of queue is called deque (double ended queue), which allows both insertion and deletion at the both ends. In JCF, the Deque interface is defined, which extends Queue interface and the Deque Interface is implemented by Linked List class (see Figure 7.24).

 

 

Figure 7.24. Class hierarchy of Queue and Dequeue

 

Few important characteristics of Queue are:

·         The Java Queue supports all methods of Collection interface including insertion, deletion, etc.

·         LinkedList, ArrayBlockingQueue and PriorityQueue are the most frequently used implementations.

·         BlockingQueues have thread-safe implementations.

·         The Queues which are available in java.util package are Unbounded Queues.

·         The Queues which are available in java.util.concurrent package are the Bounded Queues.

·         All Queues except the Deques supports insertion and removal at the tail and head of the queue respectively. The Deques support element insertion and removal at both ends.

 

Methods of Java Queue interface

Method	Description
boolean add(object)	It is used to insert the specified element into this queue and return true upon success.
boolean offer(object)	It is used to insert the specified element into this queue.
Object remove()	It is used to retrieves and removes the head of this queue.
Object poll()	It is used to retrieves and removes the head of this queue, or returns null if this queue is empty.
Object element()	It is used to retrieves, but does not remove, the head of this queue.
Object peek()	It is used to retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

Table 7.3: The methods declared by Queue interface

 

PriorityQueue class

Being an interface the queue needs a concrete class for the declaration and the most common classes are the PriorityQueue and LinkedList in Java. The PriorityQueue class includes six constructors as summarized in Table 2.

 

Constructor	Description
PriorityQueue( )	The default constructor builds an empty queue. Its starting capacity is 11.
PriorityQueue(int capacity)	This constructor builds a queue that has the specified initial capacity.
PriorityQueue(Comparator<? super E> comp)	This constructor specifies acomparator.
PriorityQueue(int capacity, Comparator<? super E> comp)	This constructor builds a queue with the specified capacity and comparator.
PriorityQueue(Collection<? extends E> c)	This constructor creates a queue which can hold a generic collection.
PriorityQueue(PriorityQueue<? extends E> c)	This constructor create queues that are initialized with the elements of the collectionpassed in c
PriorityQueue(SortedSet<? extends E> c)	This constructors create queues that are initialized with the sorted elements of the collectionpassed in c.

Table 7.4. Constructors in PriorityQueue class

 

Note: In all cases, the capacity grows automatically as elements are added with queue structure.

 

Methods of PriorityQueue class

All the methods declared in the Queue interface are fully defined in the PriorityQueue class. Further, since it is a subtype of Collections class, it inherits all the methods of it, namely size(), isEmpty(), contains() etc.

Basic operations with Queue

Java Queue supports all operations necessary to maintain a queue structure, which are summarized in Table 7.5.

Table 7.5. Basic queue operations for queue

 

Creating a queue

Following examples illustratehow to create queues. Also, some basic operations with newly created queue are illustrated.

 

Example 7.1a.

Following example illustratehow to create a queue using PriorityQueue class along with some common operations. Queue of string objects

 

import java.util.*;

 

public class QueueCreateExample1 {

   public static void main(String[] args) {

           

      Queue<String> queue = new PriorityQueue<>();

      // Adding some elements into the queue

      queue.add("one");

      queue.add("two");

      queue.add("three");

      queue.add("four");

      System.out.println(queue); // Display the contents in queue

           

      queue.remove("three");

      System.out.println(queue);

      System.out.println("Queue Size: " + queue.size());

      System.out.println("Queue Contains element 'two' or not? : " +

queue.contains("two"));

 

      // To empty the queue

      queue.clear();

   }

}

 

Example 7.1b.

Following example illustratehow to create a queue using LinkedList class along with some common operations.  Queue of integer numbers

 

import java.util.LinkedList;

import java.util.Queue;

public class QueueCreateExample2 {

  public static void main(String[] args)  {

    // Declaration of a queue using LinkedList class

    Queue<Integer> q = new LinkedList<>();

 

    // Adds elements {0, 1, 2, 3, 4} to queue

    for(int i=0; i<5; i++)

     q.add(i);

 

    // Display contents of the queue.

    System.out.println("The queue contains :"+q);

 

    // To remove the head of queue.

    int x = q.remove();

    System.out.println("The element deleted :"+ x);

    System.out.println(q);

 

    // To view the head of queue

    int head = q.peek();

    System.out.println("head of queue:"+ head);

 

    // The size of the queue

    int size = q.size();

    System.out.println("Size of queue: "+ size);

  }

}

 

 

 

Traversing a queue

Like any collection object, queue is also a collection object and it can be traversed in many ways. Following example illustrate how to create a queue of using user defined objects. This example defines a class Book and add books to queue and then print all the books object in the queue. The elements in PriorityQueue must be of Comparable type. String and Wrapper classes are Comparable by default. To add user-defined objects in PriorityQueue, you need to implement Comparable interface.

 

Example 7.2.

·         Create a queue with objects of class Book

·         Traverse the newly created queue with for-each loop

·         Remove an element and then traverse the queue with Iterator

 

 

import java.util.*;

 

class Book implements Comparable<Book>{ 

int bookId; 

String name;

String author;

String publisher; 

int quantity;

 

public Book(int id, String name, String author, String pub, int qty) { 

bookId = id; 

    this.name = name; 

this.author = author; 

    publisher = pub; 

quantity  =qty; 

}

 

// Defining the compareTo() method

public int compareTo(Book b) { 

if(bookId>b.bookId){ 

        return 1; 

}else if(bookId<b.bookId){ 

        return -1; 

}else{ 

    return 0; 

    } 

} 

} 

 

public class QueueCreateExample3 { 

public static void main(String[] args) { 

PriorityQueue<Book> queue=new PriorityQueue<Book>(); 

    //Creating Books 

    Book b1=new Book(111,"Joy with Java","Debasis Samanta","Elsevier",8); 

    Book b2=new Book(222,"Complete Java","Herbert Schildt","Oracle",6); 

    Book b3=new Book(333,"Headstart Java","Forouzan","O’Reilly",4); 

 

//Adding Books to the queue 

queue.add(b1); 

queue.add(b2); 

queue.add(b3); 

System.out.println("Traversing the queue elements:"); 

 

//Traversing queue with for-each loop

for(Book b:queue){ 

System.out.println(b.bookId+" "+b.name+" "+b.author+" "+b.publisher

+""+b.quantity); 

    } 

 

    // Removing a book from the queue

queue.remove(); 

System.out.println("After removing one book record:"); 

for(Book b:queue){ 

System.out.println(b.bookId+" "+b.name+" "+b.author+" "+b.publisher+" "+b.quantity); 

}

 

    // Adding another book into the queue

queue.add(new Book(555, "Classic Data Structures", "D. Samanta", "Prentice Hall", 9));

 

//Traversing the queue with iterator

//Iterator itr = queue.iterator(); 

//while(itr.hasNext()){ 

//System.out.println(itr.next().bookId+" "+itr.name+" "+itr.author+" "+itr.publisher+" "+itr.quantity);

//} 

}

}

 

 

Copying an array of objects to a queue

The following program illustrates how to convert a Java array to Queue using addAll() method defined in the Collection class.

 

Example 7.3:

 

import java.util.*;

 

public class ArrayToQueue {

    public static void main(String[] args) {

 

      // Create an array of String objects     

      String city[] = {"CCU","DEL","BLR","MUM","GAU"};

 

      // Declare a queue

      Queue<String> queue = new PriorotyQueue<>();

 

      // Copying the array to Queue

      Collections.addAll(queue, city);

 

      // Printing the array

      System.out.println(“Array :” + city);

 

System.out.println();

 

// Printing the queue

      System.out.println(“Queue :” + queue);

   }

}

 

 

 

Copying aqueue to an array

The following program illustrates how to copy a Queue object to an array using toArray method defined in the Collection class.

 

Example 7.4:

 

import java.util.*;

 

public class QueueToArray {

   public static void main(String[] args) {

      // Creating a queue

      Queue<String> queue = new LinkedList<>();

      queue.add("Ram");

      queue.add("123");

      queue.add("John");

      queue.add("Jaya");

      queue.add("Jim");

queue.add("!@#$%");

     

      // Copying the queue to an array of string objects

      String city[] = queue.toArray(new String[queue.size()]);

 

// Printing the array

      System.out.println(Arrays.toString(city));

System.out.println();

 

// Printing the queue

      System.out.println(“Queue :” + queue);

   }

}

 

Inserting an element into queue

A queue in Java can grow automatically. The following program shows how a queue structure can be created with ArrayBlocking class (same as PriorotyQueue class) and insert elements and queue structure grows automatically.

 

Example 7.5a.

 

import java.util.concurrent.*;

 

public class QueueInsertOperation1 {

   public static void main(String[] args) {

      BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(2);

 

      System.out.println(queue.add(1));

      System.out.println(queue.add(2));  // Maximum capacity

      System.out.println(queue);

 

      System.out.println(queue.add(3));  // Queue grows dynamically

      System.out.println(queue);

 

      // Add more … to the queue

            for(inti=9; i>0; i--)

     queue.add(i);     //Queue grows further dynamically

 

System.out.println(queue);

 }

}

 

 

Note:

add() returns true if the element is inserted into queue successfully else it return false.

 

Example 7.5b.

Like the add(), the Queue interface has the offer() operation, which is also used to insert new element into the queue. If it performs insert operation successfully, it returns “true” value. Otherwise, it returns “false” value. The following program demonstrate this functionality.

 

import java.util.concurrent.*;

 

public class QueueInsertOperation2 {

   public static void main(String[] args) {

           

      BlockingQueue<String> queue = new ArrayBlockingQueue<>(2);

 

      System.out.println(queue.offer("One"));

      System.out.println(queue.offer("Two"));

      System.out.println(queue);

      System.out.println(queue.offer("Nine"));

      System.out.println(queue);

   }

}

 

Note:

The offer() method insert an element at the end only

 

Removing element from a queue

Thee are two methods, nameltremove() and poll() can be used to perform delete operation in a queue structure. The delete operations returns the head element of the queue, if it performs successfully. Queue supports delete operation in two forms:

 

Queue.remove(): It throws java.util.NoSuchElementException exception if the operation fails.

 

Queue.poll(): It returns a special value if the operation fails. Here, special value may be either “false” or “null”

 

Example 7.6a. :Java Queue delete operations with remove() method

 

import java.util.*;

 

public class QueueRemoveOperation{

   public static void main(String[] args)    {       

      Queue<String> queue = new LinkedList<>();

      queue.offer("One");

      queue.offer("Two");          

      System.out.println(queue);         

      System.out.println(queue.remove());

      System.out.println(queue.remove());      

      System.out.println(queue.remove()); // Throws an exception

   }

}

 

 

Example 7.6b. :Java Queue delete operations with remove() method

The poll() operation is used to delete an element from the head of the queue. If it performs delete operation successfully, it returns the head element of the queue. Otherwise it returns “null” value.

 

import java.util.*;

 

public class QueuePollOperation

{

   public static void main(String[] args)

   {       

      Queue<String> queue = new LinkedList<>();

      queue.offer("One");

      queue.offer("Two");          

      System.out.println(queue);         

      System.out.println(queue.poll());

      System.out.println(queue.poll());        

      System.out.println(queue.poll());   // It returns “null”   

   }

}

 

 

Accessing an element in a Queue

 

There are two methods in Queue Interface, namely element() and peek(), which are used to access an element in a queue. Following two examples illustrates the working of the two methods.

 

 Example 7.7a. : Accessing with element() method

 

Queue.element():

The element() operation is used to retrieve an element from the head of the queue, without removing it. If it performs examine operation successfully, it returns the head element of the queue. Otherwise it throws java.util.NoSuchElementException.

 

 

import java.util.*;

 

public class QueueElementOperation {

   public static void main(String[] args) {

           

      Queue<String> queue = new LinkedList<>();

      queue.add("One");

           

      System.out.println(queue.element());

      System.out.println(queue);

      queue.clear();

      System.out.println(queue.element()); // Throws an exception

   }

}

 

Example 7.7b.Accessing with peek() method

 

Queue.peek():

The peek() operation is used to retrieve an element from the head of the queue, without removing it. If it performs examine operation successfully, it returns the head element of the queue. Otherwise it returns null value.

 

import java.util.*;

 

public class QueuePeekOperation {

   public static void main(String[] args) {

           

      Queue<String> queue = new LinkedList<>();

      queue.add("One");

           

      System.out.println(queue.peek());

      System.out.println(queue);

      queue.clear();

      System.out.println(queue.peek()); // Returns null value

   }

}

 

Note:

If we try to call peek() method on empty Queue, it returns null value, but does NOT throw an exception as shown above.

 

Java Queue categories

In Java, we can find many Queue implementations. We can broadly categorize them into the following two types

 

·         Bounded Queues

Bounded Queues are queues which are bounded by capacity that means we need to provide the max size of the queue at the time of creation. For exampleArrayBlockingQueue (see previous example).

 

·         Unbounded Queues

Unbounded Queues are queues which are NOT bounded by capacity that means we should not provide the size of the queue. For exampleLinkedList (see previous example).

 

All Queues which are available in java.util package are Unbounded Queues and Queues which are available in java.util.concurrent package are Bounded Queues.

 

In other ways, We can broadly categorize them into the following two types:

 

·         Blocking Queues

·         Non-Blocking Queues

 

All Queues which implement BlockingQueue interface are BlockingQueues and rest are Non-Blocking Queues.

 

BlockingQueues blocks until it finishes it’s job or time out, but Non-BlockingQueues do not.

 

Some Queues are Deques and some queues are PriorityQueues.

 

BlockingQueue operations

In addition to Queue’s two forms of operations, BlockingQueue’s supports two more forms as shown below.

Table 7.6.  Operations with BlockingQueue objects

 

The ArrayDeque Class

The ArrayDeque class extends AbstractCollection and implements the Deque interface. It adds no methods of its own. ArrayDeque creates a dynamic array and has no capacity restrictions. (The Deque interface supports implementations that restrict capacity, but does not require such restrictions.)

 

ArrayDeque is a generic class that has this declaration:

class ArrayDeque<E>

 

Here, E specifies the type of objects stored in the collection.

 

ArrayDeque defines the following constructors:

ArrayDeque( )

ArrayDeque(int size)

ArrayDeque(Collection<? extends E> c)

 

The first constructor builds an empty deque. Its starting capacity is 16. The second constructor builds a deque that has the specified initial capacity. The third constructor creates a deque that is initialized with the elements of the collection passed in c. In all cases, the capacity grows as needed to handle the elements added to the deque.

 

Example 7.8.

The following program demonstrates ArrayDeque by using it to create a stack:

 

import java.util.*;

class ArrayDequeDemo {

public static void main(String args[]) {

// Create an array deque.

ArrayDeque<String>adq = new ArrayDeque<String>();

 

// Use an ArrayDeque like a stack.

adq.push("A");

adq.push("B");

adq.push("D");

adq.push("E");

adq.push("F");

 

System.out.print("Popping the stack: ");

while(adq.peek() != null)

System.out.print(adq.pop() + " ");

System.out.println();

}

}

 

 

 

--- * ---